#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/6/21 14:12
# ===========================================
#       题目名称： 46. 全排列
#       题目地址： https://leetcode.cn/problems/permutations/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    """
        给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
    """

    def permute(self, nums):
        all_possibility_dict = {}  # k 当前位数 v 剩余可选的数据 [] 列表
        digit = 1  # 位数
        while digit <= len(nums):
            if all_possibility_dict:
                temp_all_possibility_dict = {}
                for k, v in all_possibility_dict.items():
                    for i in range(len(v)):
                        temp_k = list(k)
                        temp_k = temp_k.copy()
                        temp_k.append(v[i])
                        temp_k = tuple(temp_k)
                        if temp_k in temp_all_possibility_dict.keys():
                            res = temp_all_possibility_dict[temp_k]
                            res.append([v[index] for index in range(len(v)) if index != i])
                        else:
                            temp_all_possibility_dict[temp_k] = [v[index] for index in range(len(v)) if index != i]
                all_possibility_dict = temp_all_possibility_dict.copy()
            else:  # 如果为空 表示暂时没数据 需要进行铺数据
                for i in range(len(nums)):
                    all_possibility_dict[(nums[i],)] = [nums[index] for index in range(len(nums)) if index != i]
            digit += 1  # 位数 + 1
        all_possibility = all_possibility_dict.keys()
        return [list(possibility) for possibility in all_possibility]


if __name__ == '__main__':
    s = Solution()
    print("nums = [1,2,3] => %s" % s.permute(nums=[1, 2, 3]))  # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    print("nums = [0,1] => %s" % s.permute(nums=[0, 1]))  # [[0,1],[1,0]]
    print("nums = [1] => %s" % s.permute(nums=[1]))  # [[1]]
